package data_structure.tree;

import java.util.LinkedList;

/**
 * @Classname TreeOperation
 * @Description TODO
 * @Date 2021/7/21 13:48
 * @Created by Alberthch
 */
public class TreeOperation {
    // 先序遍历
    public static void preOrderTraverse (TreeNode root) {
        if (root == null) {
            return;
        } else {
            System.out.print(root.val+" ");
            preOrderTraverse(root.left);
            preOrderTraverse(root.right);
            }
        }

    // 中序遍历
    public static void inOrderTraverse (TreeNode root) {

        if (root == null) {
            return;
        } else {
            inOrderTraverse(root.left);
            System.out.print(root.val+" ");
            inOrderTraverse(root.right);
        }
    }

    // 后序遍历
    public static void postOrderTraverse (TreeNode root) {

        if (root == null) {
            return;
        } else {
            postOrderTraverse(root.left);
            postOrderTraverse(root.right);
            System.out.print(root.val+" ");
        }
    }


    // 层次遍历，按照层次顺序压进列表，再获取并弹出
    public static void levelOrderTraverse (TreeNode root) {
        // 首先判断树是非空的
        if(root == null)
            return;
        LinkedList<TreeNode> list = new LinkedList<TreeNode>();
        list.add(root);
        TreeNode currentNode;

        // 当列表是非空时
        while(!list.isEmpty())
        {
            // 获取并移除表头
            currentNode = list.poll();
            System.out.print(currentNode.val + " ");

            // 顺序的拿取左右两个树
            if(currentNode.left != null)
                list.add(currentNode.left);
            if(currentNode.right != null)
                list.add(currentNode.right);
        }
    }

    public static void main(String[] args) {
        TreeNode[] node = new TreeNode[10];//以数组形式生成一棵完全二叉树
        for(int i = 0; i < 10; i++)
        {
            node[i] = new TreeNode(i);
        }
        for(int i = 0; i < 10; i++)
        {
            if(i*2+1 < 10)
                node[i].left = node[i*2+1];
            if(i*2+2 < 10)
                node[i].right = node[i*2+2];
        }
        TreeNode root = node[0];

        System.out.print("先序遍历：");
        preOrderTraverse(root);
        System.out.println();

        System.out.print("中序遍历：");
        inOrderTraverse(root);
        System.out.println();

        System.out.print("后序遍历：");
        postOrderTraverse(root);
        System.out.println();

        System.out.print("层次遍历：");
        levelOrderTraverse(root);
    }
}
